package ssau.knyazev.fft.modules.real;

import ssau.knyazev.modules.Generator;
import ssau.knyazev.modules.Printer;

public class RealFFTModule {

	protected RealFFTModule() {	}
	


	
	public static float[][] _fft(float[][] src){
		_inverse(src);
		
		float[][] res = new float[src.length][src[0].length];
		int N = src.length;
		int size = 0;
		for (int x = src.length; x > 1; x = x >> 1){
			size++;
		}
		float[] w_list = new float[src.length*2];
		double power = 0;
		for (int i = 0; i < src.length; i++){
			power = -2*Math.PI*i/N;
			w_list[2*i] = (float)Math.cos(power);
			w_list[2*i+1] = (float)Math.sin(power);
		}
		
		float[] t1 = new float[2];
		float[] t2 = new float[2];
		float[] tem = new float[2];
		for (int q = 0; q < size; q++) {
			int step = (int) Math.pow(2, q);
			int step2 = step*2;
			boolean flagdown = true;
			int countdown = 0;
			for (int down = 0; down < N - step; down++) {
				if (flagdown) {
					boolean flagright = true;
					int countright = 0;
					for (int right = 0; right < N - step; right++) {
						if (flagright) {
							int ind = ((down % (step2))*(N/step2))*2;
							t1[0] = w_list[ind];
							t1[1] = w_list[ind+1];
							ind = ((right % (step2))*(N/step2))*2;
							t2[0] = w_list[ind];
							t2[1] = w_list[ind+1];
							
							int dsIndex = down + step;
							int rReIndex = 2*right;
							int rImIndex = 2*right+1;
							int rsReIndex = (right+step)*2;
							int rsImIndex = (right+step)*2+1;
							
							//XXX = XXX.add(a00);
							res[down][rReIndex] = src[down][rReIndex];
							res[down][rImIndex] = src[down][rImIndex];
							res[dsIndex][rReIndex] = src[down][rReIndex];
							res[dsIndex][rImIndex] = src[down][rImIndex];
							res[down][rsReIndex] = src[down][rReIndex];
							res[down][rsImIndex] = src[down][rImIndex];
							res[dsIndex][rsReIndex] = src[down][rReIndex];
							res[dsIndex][rsImIndex] = src[down][rImIndex];
							
							
							//XXX = XXX.add(w1.multy(a10));
							tem[0] = t1[0]*src[dsIndex][rReIndex] - t1[1]*src[dsIndex][rImIndex];
							tem[1] = t1[1]*src[dsIndex][rReIndex] + t1[0]*src[dsIndex][rImIndex];
							res[down][rReIndex] = res[down][rReIndex] + tem[0];
							res[down][rImIndex] = res[down][rImIndex] + tem[1];
							res[dsIndex][rReIndex] = res[dsIndex][rReIndex] - tem[0];
							res[dsIndex][rImIndex] = res[dsIndex][rImIndex] - tem[1];
							res[down][rsReIndex] = res[down][rsReIndex] + tem[0];
							res[down][rsImIndex] = res[down][rsImIndex] + tem[1];
							res[dsIndex][rsReIndex] = res[dsIndex][rsReIndex] - tem[0];
							res[dsIndex][rsImIndex] = res[dsIndex][rsImIndex] - tem[1];
							
							//XXX = XXX.add(w2.multy(a01));
							tem[0] = t2[0]*src[down][rsReIndex] - t2[1]*src[down][rsImIndex];
							tem[1] = t2[1]*src[down][rsReIndex] + t2[0]*src[down][rsImIndex];
							res[down][rReIndex] = res[down][rReIndex] + tem[0];
							res[down][rImIndex] = res[down][rImIndex] + tem[1];
							res[dsIndex][rReIndex] = res[dsIndex][rReIndex] + tem[0];
							res[dsIndex][rImIndex] = res[dsIndex][rImIndex] + tem[1];
							res[down][rsReIndex] = res[down][rsReIndex] - tem[0];
							res[down][rsImIndex] = res[down][rsImIndex] - tem[1];
							res[dsIndex][rsReIndex] = res[dsIndex][rsReIndex] - tem[0];
							res[dsIndex][rsImIndex] = res[dsIndex][rsImIndex] - tem[1];
							
							
							//XXX = XXX.add(w1.multy(w2.multy(a11)));
							float r = t2[0]*src[dsIndex][rsReIndex] - t2[1]*src[dsIndex][rsImIndex];
							float i = t2[1]*src[dsIndex][rsReIndex] + t2[0]*src[dsIndex][rsImIndex];
							tem[0] = t1[0]*r - t1[1]*i;
							tem[1] = t1[1]*r + t1[0]*i;
							res[down][rReIndex] = res[down][rReIndex] + tem[0];
							res[down][rImIndex] = res[down][rImIndex] + tem[1];
							res[dsIndex][rReIndex] = res[dsIndex][rReIndex] - tem[0];
							res[dsIndex][rImIndex] = res[dsIndex][rImIndex] - tem[1];
							res[down][rsReIndex] = res[down][rsReIndex] - tem[0];
							res[down][rsImIndex] = res[down][rsImIndex] - tem[1];
							res[dsIndex][rsReIndex] = res[dsIndex][rsReIndex] + tem[0];
							res[dsIndex][rsImIndex] = res[dsIndex][rsImIndex] + tem[1];
							
						}
						countright++;
						if (countright == step) {
							flagright = !flagright;
							countright = 0;
						}
					}
				}
				countdown++;
				if (countdown == step) {
					flagdown = !flagdown;
					countdown = 0;
				}
			}
			float[][] tmp = src;
			src = res;
			res = tmp;
		}
		return src;
	}
	
	protected static void _inverse(float[][] src){
		for (int i = 0; i < src.length; i++){
			_inverse(src[i]);
		}
		float[] arr = new float[src.length];
		for (int i = 0; i < src[0].length; i++){
			for (int j = 0; j < src.length; j++){
				arr[j] = src[j][i];
			}
			inverse(arr);
			for (int j = 0; j < src.length; j++){
				src[j][i] = arr[j];
			}
		}
	}
	
	protected static void _inverse(float[] arr){
		int arrlength = arr.length/2;
		int dl = arrlength/2;
		int st = arrlength - 1;
		int j = 0;
		for (int i = 0; i < st; i++){
			if (i < j){
				float s0 = arr[2*i];
				arr[2*i] = arr[2*j];
				arr[2*j] = s0;
				s0 = arr[2*i + 1];
				arr[2*i + 1] = arr[2*j + 1];
				arr[2*j + 1] = s0;
			}
			int k = dl;
			while (k <= j){
				j = j - k;
				k = k >> 1;
			}
			j = j + k;
		}
	}
	
	protected static void inverse(float[] arr){
		int dl = arr.length/2;
		int st = arr.length - 1;
		int j = 0;
		for (int i = 0; i < st; i++){
			if (i < j){
				float s0 = arr[i];
				arr[i] = arr[j];
				arr[j] = s0;
			}
			int k = dl;
			while (k <= j){
				j = j - k;
				k = k >> 1;
			}
			j = j + k;
		}
	}
	
	protected static float[][] transformToComplexMatrix(float[][] src){
		float[][] res = new float[src.length][src[0].length*2];
		for (int i = 0; i < src.length; i++){
			for (int j = 0; j < src.length; j++){
				res[i][j*2] = src[i][j];
			}
		}
		return res;
	}
	
	public static void main(String[] args){
		float[][] arr = Generator.generateSimpleMatrix(8);
		Printer.printVector(arr);
		long time = System.nanoTime();
		time = System.nanoTime()-time;
		System.out.println(time);
	}
	
}
